import { measureSort, testSort } from "./utils";

function shellSort(arr:number[]):number[]{
    const n = arr.length;
    let gap = Math.floor(arr.length / 2);
    while(gap > 0){
        // 对每一个子序列进行插入排序
        for(let i = gap; i<n; i++){
            let j = i;
            const temp = arr[i];
            while(j > gap - 1 && arr[j-gap] > temp){
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}


// 测试
testSort(shellSort);
// 测试时间
measureSort(shellSort, 100000);